package com.leetcode.offer.chapter5;

import java.util.*;

import static java.lang.Math.min;

/**
 * @author Dennis Li
 * @date 2020/7/17 22:18
 */
public class NthUglyNumber_49 {

    public int nthUglyNumber(int n) {
        if (n == 1) return 1;
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        int[] ints = new int[4];


        int i = list.size() - 1;
        int two = 2, three = 3, five = 5;
        while (i < n) {
            two = min(list.get(i - 1) * 2, two);
            three = min(list.get(i - 2) * 3, three);
            five = min(list.get(i - 3) * 5, five);
            list.add(min(two, min(three, five)));
            i++;
        }
        return list.get(n - 1);
    }

    public int nthUglyNumber2(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        // 核心在于通过三个序号来标识位置，和遍历的位置要区分开
        for (int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = min(n2, min(n3, n5));
            if (dp[i] == n2) a++;
            if (dp[i] == n3) b++;
            if (dp[i] == n5) c++;
        }
        return dp[n - 1];
    }

}
